#include <iostream>

using namespace std;

int partition(int * arr, int left, int right, int pivotIndex){
	int pivot = arr[pivotIndex];
	int tmp;
	do {
		while (arr[left] < pivot) left++;
		while (arr[right] > pivot) right--;
		if (left < right && arr[left] != arr[right]){
			tmp = arr[left];
			arr[left] = arr[right];
			arr[right] = tmp;
		} else {
			return right;
		}
	} while(left < right);
	return right;
}

void quicksort(int * arr, int left, int right){
	if (left < right){
		int pivot = (left + right) >> 1;
		int mid = partition(arr, left, right, pivot);
		quicksort(arr, left, mid - 1);
		quicksort(arr, mid + 1, right);
	}
}

void printArray(int * arr, int left, int right){
	for (int i = left; i <= right; i++)
		cout <<arr[i] <<" ";
	cout <<endl;
}

int quicksortTest(){
	int arr[] = {-1, 3, -10, 5, 1, 34, 3, 7};

	quicksort(arr, 0, 7);

	printArray(arr, 0, 7);

	cin.get();

	return 0;
}